翻訳と辞書 Words near each other ・ Exa TV ・ Exa- ・ Exabit ・ ExAblate ・ Exabyte ・ Exabyte (company) ・ Exacerbation ・ Exact (software company) ・ Exact Air ・ Exact algorithm ・ Exact Audio Copy ・ Exact C*-algebra ・ Exact category ・ Exact Change ・ Exact coloring ・ Exact cover ・ Exact Data ・ Exact differential ・ Exact differential equation ・ Exact division ・ Exact Editions ・ Exact Equation ・ Exact functor ・ Exact Sciences (company) ・ Exact sequence ・ Exact solutions in general relativity ・ Exact solutions of classical central-force problems ・ Exact statistics ・ Exact test ・ ExactEarth Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Exact cover ： ウィキペディア英語版 Exact cover In mathematics, given a collection $\backslash mathcal$ of subsets of a set ''X'', an exact cover is a subcollection $\backslash mathcal^$ * of $\backslash mathcal$ such that each element in ''X'' is contained in ''exactly one'' subset in $\backslash mathcal^$ *. One says that each element in ''X'' is covered by exactly one subset in $\backslash mathcal^$ *. An exact cover is a kind of cover. In computer science, the exact cover problem is a decision problem to determine if an exact cover exists. The exact cover problem is NP-complete〔 This book is a classic, developing the theory, then cataloguing ''many'' NP-Complete problems. 〕 and is one of Karp's 21 NP-complete problems.〔 〕 The exact cover problem is a kind of constraint satisfaction problem. An exact cover problem can be represented by an incidence matrix or a bipartite graph. Knuth's Algorithm X is an algorithm that finds all solutions to an exact cover problem. DLX is the name given to Algorithm X when it is implemented efficiently using Donald Knuth's Dancing Links technique on a computer.〔 The standard exact cover problem can be generalized slightly to involve not only "exactly one" constraints but also "at-most-one" constraints. Finding Pentomino tilings and solving Sudoku are noteworthy examples of exact cover problems. The N queens problem is a slightly generalized exact cover problem. == Formal definition == Given a collection $\backslash mathcal$ of subsets of a set ''X'', an exact cover of ''X'' is a subcollection $\backslash mathcal^$ * of $\backslash mathcal$ that satisfies two conditions: * The intersection of any two distinct subsets in $\backslash mathcal^$ * is empty, i.e., the subsets in $\backslash mathcal^$ * are pairwise disjoint. In other words, each element in ''X'' is contained in ''at most one'' subset in $\backslash mathcal^$ *. * The union of the subsets in $\backslash mathcal^$ * is ''X'', i.e., the subsets in $\backslash mathcal^$ * cover ''X''. In other words, each element in ''X'' is contained in ''at least one'' subset in $\backslash mathcal^$ *. In short, an exact cover is "exact" in the sense that each element in ''X'' is contained in ''exactly one'' subset in $\backslash mathcal^$ *. Equivalently, an exact cover of ''X'' is a subcollection $\backslash mathcal^$ * of $\backslash mathcal$ that partitions ''X''. For an exact cover of ''X'' to exist, it is necessary that: * The union of the subsets in $\backslash mathcal$ is ''X''. In other words, each element in ''X'' is contained in at least one subset in $\backslash mathcal$. If the empty set ∅ is contained in $\backslash mathcal$, then it makes no difference whether or not it is in any exact cover. Thus it is typical to assume that: * The empty set is not in $\backslash mathcal^$ *. In other words, each subset in $\backslash mathcal^$ * contains at least one element. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Exact cover」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.